'''
Created on Apr 12, 2012

@author: dolphinigle
'''

import random
import util

def IsPrime(number):
  '''
  Probabilistic using Fermat primality check.
  '''
  for _ in range(3000):
    test = random.randrange(1, number)
    if util.ModExp(test, number-1, number) != 1:
      return False
  
  return True

def Generate(minbits, maxbits):
  while True:
    test = random.randrange(2**minbits, 2**(maxbits+1))
    if IsPrime(test):
      return test
